home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / THINKC / 4_0 / MANDLE_C / MANDCRAW.C < prev   
Text File  |  1990-05-06  |  6KB  |  232 lines
  1. /*    Copyright 1988,1989 by Scott Sherman and John Gossman
  2.     
  3.     The following C code is for a fast Mandelbrot Algorithm
  4.     called Contour Crawling, invented by Scott Sherman in 1986 while a
  5.     math student at Western Washington Univ.  The algorithm    works by 
  6.     scanning across the Mandelbrot Set point by point, looking
  7.     for regions of the same color.  Once a "Contour" is detected, the
  8.     algorithm bounces back and forth along the boundary of the contour
  9.     until it finds its way back to its starting point, and then fills the
  10.     interior.  Intuitively and in practice it is far more efficient than
  11.     the normal pixel by pixel method or Mariani's Method.  The following
  12.     code should demonstrate that it is also simple.  Scott and I (John
  13.     Gossman) have written an article about Contour Crawling that covers
  14.     the theoretical aspects and such concerns as "Islands", the connected
  15.     nature of the level sets around the Mandelbrot Set, and the practical
  16.     issues of Contour Crawling on a discrete lattice.  I will post this
  17.     article somewhere soon, and leave a note here about getting hold of
  18.     it.  The best argument is to code up a version of this program and
  19.     look at the results.  Another nice thing is that all the optimization
  20.     tricks for calculating the count (assembly, fixed-point etc.) can still 
  21.     be applied to this method in order to further increase the speed.
  22. */
  23.  
  24. /*
  25. Keywords to be defined :
  26.     MINX,    ; These four define the resolution
  27.     MINY,
  28.     MAXX,
  29.     MAXY,
  30.     BIGGESTCOUNT,    ; the maximum iterations for GetCount
  31.     BLANK,        ; normally 0
  32.     LIMIT        ; Use 4 or 5.  Used to recognize contours.
  33.     GETPIXEL(),     ; A function to read a pixel value
  34.     PUTPIXEL(),    ; A function to set a pixel value
  35.  
  36. */
  37. #define MINX    0
  38. #define MINY    0
  39. #define MAXX    500
  40. #define MAXY    400
  41. #define BIGGESTCOUNT    255
  42. #define BLANK    0
  43. #define LIMIT    4
  44.  
  45. extern Boolean HALT;
  46.  
  47. int maxcount;
  48. int new;
  49. double xr[MAXX+1];
  50. double yr[MAXY+1];
  51. int color[BIGGESTCOUNT];
  52.  
  53. /* (x_coord,y_coord) contain the screen coordinates of the point
  54.    return the count of the point */
  55. int GetCount(x_coord,y_coord)
  56. int x_coord,y_coord;
  57. {
  58.     double x,y;
  59.     double cx,cy;
  60.     double x2,y2;
  61.     int count;
  62.  
  63.     count = 1;
  64.     x = xr[x_coord];y = yr[y_coord];
  65.     cx = x;    cy = y;
  66.     x2 = x*x;y2 = y*y;
  67.  
  68.     while ((x2 + y2 < 4) && (count < maxcount))
  69.         {
  70.         y = 2*x*y + cy;
  71.         x = x2-y2 + cx;
  72.         x2 = x*x;
  73.         y2 = y*y;
  74.         count = count + 1;
  75.         }
  76.     return (count);
  77. }
  78.  
  79. /* (x,y) contain the screen coordinates of a point
  80.    return its color
  81.     if the point is off the screen, return BLANK
  82.     if the point was freshly calculated, display it & new = TRUE
  83. */
  84. int _GetColor(x,y)
  85. int x,y;
  86. {
  87.     int temp,GetCount();
  88.     int GETPIXEL();
  89.  
  90.     if ((x<MINX) || (x>MAXX) || (y<MINY) || (y>MAXY))
  91.         return (BLANK);
  92.     temp = GETPIXEL(x,y);
  93.     if (temp == BLANK)
  94.         {
  95.         new = TRUE;
  96.         temp = GetCount(x,y);
  97.         temp = color[temp];
  98.         PUTPIXEL(x,y,temp);
  99.         }
  100.     else new = FALSE;
  101.     return (temp);
  102. }
  103.  
  104. /* (x,y) contain the screen coordinates of the point
  105.    If this point hasn't been calculated before, return TRUE */
  106. int IsBlank(x,y)
  107. int x,y;
  108. {
  109.     if ((x<MINX) || (x>=MAXX) || (y<MINY) || (y>=MAXY))
  110.         return FALSE;
  111.     return (GETPIXEL(x,y) == BLANK);
  112. }
  113.  
  114. /* (x,y) contain the screen coordinates of a point on a contour
  115.     'thecount' contains the value of the contour
  116.    if 'fill' is FALSE, crawl the region
  117.     if 'fill' is TRUE, fill the region */
  118. void Crawl(x,y,thecount,fill)
  119. int x,y;
  120. int thecount;
  121. int fill;
  122. {
  123.     int xinc,yinc;        /* direction to travel */
  124.     int firstx,firsty;        /* the starting & ending point */
  125.     int done;            /* we've reached the end */
  126.     int _GetColor(),IsBlank();
  127.  
  128.     firstx = x;
  129.     firsty = y;
  130.     xinc = 1;
  131.     done = FALSE;
  132.  
  133.     while (!done)
  134.         {
  135.         if (HALT) goto out;
  136.         if (_GetColor(x+xinc,y) == thecount)
  137.             {
  138.             x = x + xinc;
  139.             yinc = -xinc;
  140.             done = (x==firstx) && (y==firsty);
  141.             if (fill && IsBlank(x-yinc,y))
  142.                 FillLine(x-yinc,y,yinc,thecount);
  143.             }
  144.         else yinc = xinc;
  145.         if (!done && (_GetColor(x,y+yinc) == thecount))
  146.             {
  147.             y = y + yinc;
  148.             xinc = yinc;
  149.             done = (x==firstx) && (y==firsty);
  150.             if (fill && IsBlank(x-yinc,y))
  151.                 FillLine(x-yinc,y,yinc,thecount);
  152.             }
  153.         else xinc = -yinc;
  154.         }
  155.     if (!fill)
  156.         Crawl(firstx,firsty,thecount,TRUE);
  157. out:
  158.     ;
  159. }
  160.  
  161. /* (leftx,topy) contain the real coordinates of the upper left
  162.     corner of the region - 'gap' is the length of a side
  163.    calculate the cooresponding region of the Mandelbrot Set */
  164. DisplaySet(leftx,topy,gap)
  165. double leftx,topy,gap;
  166. {
  167.     double smallgap;        /* real width of a pixel */
  168.     int last,count;        /* last count & present count */
  169.     int edge,edgex,edgey;    /* screen coords of edge of contour */
  170.     int x,y;            /* current screen coordinates */
  171.     int _GetColor();
  172.  
  173.     smallgap = gap/MAXY;
  174.     for (x=MINX; x<=MAXX; x++)
  175.         xr[x] = leftx + (x-MINX) * smallgap;
  176.     for (y=MINY; y<=MAXY; y++)
  177.         yr[y] = topy - (y-MINY) * smallgap;
  178.  
  179.     edge = 0;
  180.     last = BLANK;
  181.  
  182.     for (x=MINX; x<=MAXX; x++)
  183.         {
  184.         for (y=MINY; y<=MAXY; y++)
  185.             {
  186.             if (HALT) goto out;
  187.             
  188.             count = _GetColor(x,y);
  189.             if (count == last)
  190.                 edge++;
  191.             else    {
  192.                 last = count;
  193.                 edge = 0;
  194.                 edgex = x;
  195.                 edgey = y;
  196.                 }
  197.             if (new && edge>=LIMIT)
  198.                 Crawl(edgex,edgey,count,FALSE);
  199.             }
  200.         edge = 0;
  201.         last = BLANK;
  202.         }
  203. out:
  204.     ;
  205. }
  206.  
  207. /* To make contour crawling faster and generate prettier pictures
  208. with less "noise" near the edge of the Mandelbrot Set, you can
  209. combine level sets.  The following fragment combines every other
  210. band on a 16 color system.  A more sophisticated approach is to
  211. combine bands logarithmically, so that outer bands do not get 
  212. combined and narrow bands near the MandelBrot set get clumped
  213. together in groups of hundreds.  IMPORTANT: This not only makes the
  214. algorithm faster it makes better looking pictures.
  215.  
  216. I removed this extensive color stuff because the Mac has 8-bit graphics */
  217.  
  218. /* a sample of how the bands could be combined */
  219. GENERATECOUNTS(color,maxcount)
  220. int color[];
  221. int maxcount;
  222. {
  223.     int i;
  224.  
  225.     for (i=0; i<maxcount; i++)
  226.         color[i] = (i % 255);
  227. }
  228.  
  229.  
  230.  
  231.  
  232.